找传奇、传世资源到传世资源站!

python素数应用

8.5玩家评分(1人评分)
下载后可评
介绍 评论 失效链接反馈

#求一个数的比自己小的所有互质数的算法
#队列关系:a d N,a = (a d N) % N,由a和N求d
#类似环形队列:初始点a不影响计算,实则由N求d
N = 840#求一个数的所有因数
def get_factor(a):
 l = []
 for i in range(1,a 1): #输出1~(a-1)
  if (a % i) == 0:
   l.append(i)
 return l#判断2个数是否互质:公约(因)数只有1的两个数叫做互质数。
def is_coprime(a,b):
 a1 = get_factor(a)
 a1.remove(1)
 a2 = get_factor(b)
 a2.remove(1)
 for i in a1:
  for j in a2:
   if j == i:
    return 0
 return 1# x * D (x 属于1~N)除不尽 N
l1 = []
for d in range(1,N):
 for i in range(1,N):
  if ((i * d) % N) != 0: #在N-1次循环中除不够即为所需
   if i == (N - 1):
    l1.append(d) #全满足
   continue #继续执行下一轮判断
  else:
   break; #不到N就除尽不满足 
print(l1)l2 = []
for i in range(1,N):
 if is_coprime(i,N) == 1:
  l2.append(i)
print(l2)

评论

发表评论必须先登陆, 您可以 登陆 或者 注册新账号 !


在线咨询: 问题反馈
客服QQ:174666394

有问题请留言,看到后及时答复